package LearnAlgorithm.f_字符串;


/*
实现一个算法，确定一个字符串的所有字符是否全都不同。
假使不允许使用额外的数据结构，又该如何处理? 

开始，不妨先问问面试官，上面的字符串是ASCII字符串还是Unicode字符串。 
这很重要，
问这个问题表明你关注细节，并且对计算机科学有深刻了解
为了简单起见，这里假定字符集为ASCII。若不是的话，则需扩大存储空间，不过其余逻辑没有分别。
假定字符集为ASCII,对于这个问题，我们可以做1个简单的优化，
若字符串的长度大于字母表中的字符个数，则直接返回false
毕竟,若字母表只有256个字符,字符串里就不可能有280个各不相同的字符
 */
public class a判断单个字符串元素全不同 {
	public static void main(String[] args) {
		String string = "abcdefg";
		String string2 = "aacdefg";
		System.out.println(compare(string));
		System.out.println(compare(string2));
	}
	
	/**
	 * O(N)
	 * 针对默认的ASCII字符集的字符串
	 * @param a
	 * @return
	 */
	public static boolean compare(String a) {
		if (a.length() == 0 || a == null ) {
			System.out.println("空串所以肯定不同");
			return true;
		}
		int[] flag = new int[128];
		for (int i = 0; i < a.length(); i++) {
			if (flag[(int) a.charAt(i)] > 0) {
				return false;
			}
			flag[(int) a.charAt(i)]++;
		}
		return true;
	}
}
